//希尔排序
#pragma once
//希尔排序
template <typename E>
void ShellSort(E a[], int n)
{
    int dk = n / 2;
    while (dk >= 1)
    {
        // -趟增量dk的希尔排序
        for (int i = dk; i < n; i++)
        {
            E x = a[i];
            int j;
            for (j = i - dk; j >= 0 && x < a[j]; j -= dk)
                a[j + dk] = a[j];
            a[j + dk] = x;
        }
        //缩小增量
        dk /= 2;
    }
}